/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  // const f = new Array(m).fill(0).map(()=> new Array(n).fill(0));
  const f = new Array(m);
  for (let i = 0; i < m; i++) {
    f[i] = new Array(n).fill(0);
  }
  for (let i = 0; i < m; i++) {
    if (obstacleGrid[i][0] === 1) {
      break;
    }
    f[i][0] = 1;
  }
  for (let i = 0; i < n; i++) {
    if (obstacleGrid[0][i] === 1) {
      break;
    }
    f[0][i] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] === 1) {
        continue;
      }
      f[i][j] = f[i - 1][j] + f[i][j - 1];
    }
  }

  return f[m - 1][n - 1];
};

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
// 这个是 ai 的回答，貌似比较的好
/* 
方法思路
初始化 DP 数组：创建一个与输入网格大小相同的二维数组dp，其中dp[i][j]表示从左上角到位置(i, j)的不同路径数量。
处理边界条件：
如果起点或终点有障碍物，直接返回 0，因为无法到达。
初始化dp[0][0]为 1，表示起点的路径数量为 1。
处理第一行和第一列：如果当前位置没有障碍物且前一个位置可达，则当前位置的路径数量等于前一个位置的路径数量；否则为 0。
状态转移方程：对于其他位置(i, j)，如果当前位置没有障碍物，则路径数量为上方(i-1, j)和左方(i, j-1)的路径数量之和；否则为 0。
结果：右下角的dp[m-1][n-1]即为所求的不同路径数量。
*/
var uniquePathsWithObstacles = function (obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;

  // 如果起点或终点有障碍物，直接返回0
  if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) {
    return 0;
  }

  const dp = Array.from({ length: m }, () => Array(n).fill(0));

  // 初始化起点
  dp[0][0] = 1;

  // 初始化第一行
  for (let j = 1; j < n; j++) {
    dp[0][j] = obstacleGrid[0][j] === 0 && dp[0][j - 1] === 1 ? 1 : 0;
  }

  // 初始化第一列
  for (let i = 1; i < m; i++) {
    dp[i][0] = obstacleGrid[i][0] === 0 && dp[i - 1][0] === 1 ? 1 : 0;
  }

  // 填充剩余的dp数组
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] === 0) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      } else {
        dp[i][j] = 0;
      }
    }
  }

  return dp[m - 1][n - 1];
};